package Lab9;

import java.util.Arrays;
import java.util.Comparator;

public class MergeSort {
    public static <E extends Comparable<E>> void mergeSort(E[] list) {
        mergeSort(list, Comparator.naturalOrder());
    }

    public static <E> void mergeSort(E[] list, Comparator<? super E> comparator) {
        if (list.length > 1) {
            int mid = list.length / 2;
            E[] l_half = Arrays.copyOfRange(list, 0, mid);
            mergeSort(l_half, comparator);
            E[] r_half = Arrays.copyOfRange(list, mid, list.length); //(E[]) new Object[list.length - mid];
            mergeSort(r_half, comparator);

            merge(l_half, r_half, list, comparator);
        }
    }

    private static <E> void merge(E[] l_half, E[] r_half, E[] list, Comparator<E> comparator) {
        int a = 0;
        int b = 0;
        int c = 0;
        while (a < l_half.length && b < r_half.length) {
            if (comparator.compare(l_half[a], r_half[b]) < 0) {
                list[c++] = l_half[a++];
            } else {
                list[c++] = r_half[b++];
            }
        }

        if(a<l_half.length){
            for(; a<l_half.length; a++){
                list[c++] = l_half[a];
            }
        }else{
            while(b<r_half.length){
                list[c++] = r_half[b++];
            }
        }
    }


    public static void main(String[] args) {
        Integer[] ls = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};

        mergeSort(ls, Comparator.reverseOrder()); //(e1, e2) -> e2.compareTo(e1)
        System.out.println(Arrays.toString(ls));
        mergeSort(ls);
        System.out.println(Arrays.toString(ls));


    }
}
